/*
	解法：两重for + 双指针
	为什么：官方题解
	时间复杂度：O(n³)，空间复杂度：O(log n) 排序空间+O(k)返回值空间
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
public:
	vector<vector<int>> fourSum(vector<int> &nums, int target)
	{
		vector<vector<int>> res;
		if (nums.size() < 4)
		{
			return res;
		}
		
		sort(nums.begin(), nums.end());
		int length = nums.size();
		
		for (int i = 0; i < length - 3; i++)
		{
			//需要和上一次枚举的a不同，目的：去重
			if (i > 0 && nums[i] == nums[i - 1])
			{
				continue;
			}
			
			//当前最小的和已经大于 target，后面更大更不可能满足，直接终止最外层循环
			if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
			{
				break;
			}
			
			//当前 i 开头的任何组合都不可能达到 target, 于是应该跳过当前 i 去试下一个更大的 i
			if ((long)nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target)
			{
				continue;
			}
			
			for (int j = i + 1; j < length - 2; j++)
			{
				//需要和上一次枚举的a不同，目的：去重
				if (j > i + 1 && nums[j] == nums[j - 1])
				{
					continue;
				}
				
				//当前最小的和已经大于 target，后面更大更不可能满足，直接终止第二层循环
				if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
				{
					break;
				}
				
				//当前 j 开头的任何组合都不可能达到 target, 于是应该跳过当前 j 去试下一个更大的 j
				if ((long)nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target)
				{
					continue;
				}
				
				int left = j + 1;
				int right = length - 1;
				
				while (left < right)
				{
					long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
					
					if (sum == target)
					{
						res.push_back({nums[i], nums[j], nums[left], nums[right]});
						
						//已经用 nums[left] 参与过一次命中的四元组了（sum == target），接下来要找新的配对，必须把 left 移到下一个不同的值；只在 while 里停下的话，left 仍停在那串重复值的最后一个相同元素上
						while (left < right && nums[left] == nums[left + 1])
						{
							left++;
						}
						left++;
						
						//right同理
						while (left < right && nums[right] == nums[right - 1])
						{
							right--;
						}
						right--;
					}
					else if (sum < target)
					{
						left++;
					}
					else
					{
						right--;
					}
				}
			}
		}
		
		return res;
	}
};


int main()
{
	Solution solution;
	vector<int> nums = {1, 0, -1, 0, -2, 2};
	int target = 0;
	
	vector<vector<int>> result = solution.fourSum(nums, target);
	
	cout << "结果为：" << endl;
	for (const auto &quad : result)
	{
		cout << "[ ";
		for (int num : quad)
		{
			cout << num << " ";
		}
		cout << "]" << endl;
	}
	
	return 0;
}




